package org.lql.algo.codecrush.hot100.dynamicProgramming;

import java.util.Arrays;

/**
 * @author: liangqinglong
 * @date: 2025-09-13 14:48
 * @description: 416. 分割等和子集 <a href="https://leetcode.cn/problems/partition-equal-subset-sum/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class CanPartition {

	public boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if (sum % 2 != 0) {
			return false;
		}
		// 初始化动态规划数组，dp[j]表示是否可以使用数组中的部分元素凑出和为j
		int target = sum / 2;
		int[] dp = new int[target + 1];
		for (int num : nums) {
			for (int j = target; j >= num; j--) {
				// 如果当前和j能够由之前的和j-num加上当前元素num得到，且这个和更大，则更新dp[j]
				dp[j] = Math.max(dp[j], dp[j - num] + num);
			}
		}
		System.out.println(Arrays.toString(dp));
		return dp[target] == target;
	}

	public static void main(String[] args) {
		CanPartition canPartition = new CanPartition();
		System.out.println(canPartition.canPartition(new int[]{1, 5, 11, 5}));
		System.out.println(canPartition.canPartition(new int[]{1, 2, 3, 5}));
	}
}
